import java.util.LinkedList;
import java.util.Queue;

public class Graph {
    //顶点数量
    int nodeNum, edgeNum;
    //顶点数组
    int node[];
    //邻接矩阵
    int arc[][];

    public static void main(String[] args) {

        Graph g = new Graph();
        int[][] a = g.setArray();
        g = g.initGraph(g, a);
        // g.bfs(g);
        int[] visitted = new int[5];
        for (int i = 0; i < g.nodeNum; i++)
            if (visitted[i] == 0) {
                g.dfs(g, i, visitted);
            }

    }

    public Graph initGraph(Graph g, int[][] a) {
        g.nodeNum = a.length;
        int sum = 0;
        g.arc = new int[a.length][a.length];
        g.arc = a;

        for (int i = 0; i < a.length; i++) {
            for (int j = 0; j < a.length; j++) {
                sum += a[i][j];
                //g.arc[i][j] = a[i][j];
            }

        }
        g.edgeNum = sum;
        g.node = new int[a.length];
        for (int i = 0; i < a.length; i++)
            g.node[i] = i;
        return g;
    }

    int[][] setArray() {
        int[][] a = new int[5][5];
        for (int i = 0; i < 5; i++)
            for (int j = 0; j < 5; j++)
                a[i][j] = 0;
        int[][] edges = new int[][]{{0, 1}, {0, 2}, {1, 3}, {1, 4}, {2, 3}, {2, 4}};
        for (int[] ls : edges) {
            a[ls[0]][ls[1]] = 1;
            a[ls[1]][ls[0]] = 1;
        }
        return a;

    }

    void dfs(Graph g, int i, int[] visited) {
        //递归实现，类似树的先序遍历
        visited[i] = 1;
        System.out.println(i);
        for (int j = 0; j < g.nodeNum; j++)
            if (g.arc[i][j] == 1 && visited[j] == 0)
                g.dfs(g, j, visited);
    }

    //无向图
    void bfs(Graph g) {
        if (g == null) System.out.println("图为空");
        else {
            //借助队列实现 类似树的层次遍历
            Queue<Integer> q = new LinkedList<Integer>();
            q.offer(g.node[0]);
            Queue<Integer> visited = new LinkedList<Integer>();
            visited.offer(g.node[0]);
            int index = 0;
            System.out.println("第" + (index++) + "个结点:0");
            int[][] arc = g.arc;

            while (!q.isEmpty()) {

                int thisNode = q.poll();

                /*
                    01100
                    10011
                    10011
                    01100
                    01100
                    * */
                for (int i = thisNode; i < arc.length; i++)
                    //如果存在边且顶点未访问，入队
                    if (arc[thisNode][i] == 1 && !visited.contains(i)) {
                        q.offer(i);
                        visited.offer(i);
                        System.out.println("第" + (index++) + "个结点:" + i);
                    }
            }
            //处理孤立结点
            for (int node : g.node)
                if (!visited.contains(node))
                    System.out.println("第" + (index++) + "个结点:" + node);
        }
    }
}
